#include <algorithm>
#include <cstdint>
#include <functional>
#include <iostream>
#include <istream>
#include <limits>
#include <ostream>
#include <queue>
#include <utility>
#include <vector>

using ll = int64_t;

const ll max_m = 1e4 + 5, max_n = max_m, inf = std::numeric_limits<ll>::max();
ll n, m, s, dists[max_n];
struct Edge{
    ll u,v,x,y,t;
}edges[max_m];

int main(){
    std::iostream::sync_with_stdio(false), std::cin.tie(nullptr), std::cout.tie(nullptr);

    std::fill(dists, dists+max_n, inf);

    std::cin>>n>>m>>s;
    dists[s]=0;
    for(ll i{1};i<=m;i++){
        
        const auto swap_big_small = []<class T>(T &a, T &b)->void{
            if(a>b){std::swap(a,b);}
        };
        std::cin>>edges[i].u>>edges[i].v>>edges[i].x>>edges[i].y>>edges[i].t;
        swap_big_small(edges[i].u, edges[i].v);
        swap_big_small(edges[i].x, edges[i].y);
    }
    
    std::priority_queue<std::pair<ll, ll>, std::vector<std::pair<ll, ll>>, std::greater<>> pq;
    pq.emplace(0, s);
    while(!pq.empty()){
        const auto [dist,now] = pq.top();
        pq.pop();
        if(dist > dists[now])continue;
        for(ll i{1};i<=m;i++){
            if(edges[i].u<=now && now<=edges[i].v){
                for(ll target{edges[i].x}; target<=edges[i].y; ++target){
                    if(dists[target] > dist + edges[i].t){
                        dists[target] = dist + edges[i].t;
                        pq.emplace(dists[target], target);
                    }
                }
            }
            if(edges[i].x <= now && now<=edges[i].y){
                for(ll target{edges[i].u}; target<=edges[i].v; ++target){
                    if(dists[target] > dist + edges[i].t){
                        dists[target] = dist + edges[i].t;
                        pq.emplace(dists[target], target);
                    }
                }
            }
        }
    }

    for(ll i{1};i<=n;i++){
        std::cout<<(dists[i]==inf?-1ll:dists[i])<<' ';
    }
    std::cout<<'\n'<<std::flush;
}